package cn.hy.today;

import java.util.*;

class Solution_2454 {
    public int[] secondGreaterElement(int[] nums) {
        int[] ans = new int[nums.length];
        Arrays.fill(ans, -1);
        Deque<Integer> stack = new ArrayDeque<>();
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        for (int i = 0; i < nums.length; i++) {
            //1.若该 pq 非空且堆顶元素小于当前遍历的元素时，说明当前元素为堆顶元素的「第二大」的整数，
            // 我们取出堆顶元素，并更新结果数组。重复该操作直至 q 为空或者堆顶元素大于等于当前遍历元素。
            while (!pq.isEmpty() && pq.peek()[0] < nums[i]) {
                ans[pq.poll()[1]] = nums[i];
            }
            //2. 若 stack 非空且栈顶元素对应的值小于当前遍历元素，则说明找到了栈顶元素的下一个更大的数字，将栈顶元素出栈，
            // 并加入堆 pq 中。重复执行该操作直至 stack 为空或者栈顶元素大于等于当前遍历元素。
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                pq.offer(new int[]{nums[stack.peek()], stack.peek()});
                stack.pop();
            }
            // 3. 将当前元素的下标压入栈 stack 中。
            stack.push(i);
        }
        return ans;
    }
}